home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / hity wydania / Ubuntu 9.10 PL / karmelkowy-koliberek-desktop-9.10-i386-PL.iso / casper / filesystem.squashfs / usr / lib / python2.6 / _abcoll.py < prev    next >
Text File  |  2009-11-02  |  14KB  |  563 lines
  1. # Copyright 2007 Google, Inc. All Rights Reserved.
  2. # Licensed to PSF under a Contributor Agreement.
  3.  
  4. """Abstract Base Classes (ABCs) for collections, according to PEP 3119.
  5.  
  6. DON'T USE THIS MODULE DIRECTLY!  The classes here should be imported
  7. via collections; they are defined here only to alleviate certain
  8. bootstrapping issues.  Unit tests are in test_collections.
  9. """
  10.  
  11. from abc import ABCMeta, abstractmethod
  12. import sys
  13.  
  14. __all__ = ["Hashable", "Iterable", "Iterator",
  15.            "Sized", "Container", "Callable",
  16.            "Set", "MutableSet",
  17.            "Mapping", "MutableMapping",
  18.            "MappingView", "KeysView", "ItemsView", "ValuesView",
  19.            "Sequence", "MutableSequence",
  20.            ]
  21.  
  22. ### ONE-TRICK PONIES ###
  23.  
  24. class Hashable:
  25.     __metaclass__ = ABCMeta
  26.  
  27.     @abstractmethod
  28.     def __hash__(self):
  29.         return 0
  30.  
  31.     @classmethod
  32.     def __subclasshook__(cls, C):
  33.         if cls is Hashable:
  34.             for B in C.__mro__:
  35.                 if "__hash__" in B.__dict__:
  36.                     if B.__dict__["__hash__"]:
  37.                         return True
  38.                     break
  39.         return NotImplemented
  40.  
  41.  
  42. class Iterable:
  43.     __metaclass__ = ABCMeta
  44.  
  45.     @abstractmethod
  46.     def __iter__(self):
  47.         while False:
  48.             yield None
  49.  
  50.     @classmethod
  51.     def __subclasshook__(cls, C):
  52.         if cls is Iterable:
  53.             if any("__iter__" in B.__dict__ for B in C.__mro__):
  54.                 return True
  55.         return NotImplemented
  56.  
  57. Iterable.register(str)
  58.  
  59.  
  60. class Iterator(Iterable):
  61.  
  62.     @abstractmethod
  63.     def next(self):
  64.         raise StopIteration
  65.  
  66.     def __iter__(self):
  67.         return self
  68.  
  69.     @classmethod
  70.     def __subclasshook__(cls, C):
  71.         if cls is Iterator:
  72.             if any("next" in B.__dict__ for B in C.__mro__):
  73.                 return True
  74.         return NotImplemented
  75.  
  76.  
  77. class Sized:
  78.     __metaclass__ = ABCMeta
  79.  
  80.     @abstractmethod
  81.     def __len__(self):
  82.         return 0
  83.  
  84.     @classmethod
  85.     def __subclasshook__(cls, C):
  86.         if cls is Sized:
  87.             if any("__len__" in B.__dict__ for B in C.__mro__):
  88.                 return True
  89.         return NotImplemented
  90.  
  91.  
  92. class Container:
  93.     __metaclass__ = ABCMeta
  94.  
  95.     @abstractmethod
  96.     def __contains__(self, x):
  97.         return False
  98.  
  99.     @classmethod
  100.     def __subclasshook__(cls, C):
  101.         if cls is Container:
  102.             if any("__contains__" in B.__dict__ for B in C.__mro__):
  103.                 return True
  104.         return NotImplemented
  105.  
  106.  
  107. class Callable:
  108.     __metaclass__ = ABCMeta
  109.  
  110.     @abstractmethod
  111.     def __call__(self, *args, **kwds):
  112.         return False
  113.  
  114.     @classmethod
  115.     def __subclasshook__(cls, C):
  116.         if cls is Callable:
  117.             if any("__call__" in B.__dict__ for B in C.__mro__):
  118.                 return True
  119.         return NotImplemented
  120.  
  121.  
  122. ### SETS ###
  123.  
  124.  
  125. class Set(Sized, Iterable, Container):
  126.     """A set is a finite, iterable container.
  127.  
  128.     This class provides concrete generic implementations of all
  129.     methods except for __contains__, __iter__ and __len__.
  130.  
  131.     To override the comparisons (presumably for speed, as the
  132.     semantics are fixed), all you have to do is redefine __le__ and
  133.     then the other operations will automatically follow suit.
  134.     """
  135.  
  136.     def __le__(self, other):
  137.         if not isinstance(other, Set):
  138.             return NotImplemented
  139.         if len(self) > len(other):
  140.             return False
  141.         for elem in self:
  142.             if elem not in other:
  143.                 return False
  144.         return True
  145.  
  146.     def __lt__(self, other):
  147.         if not isinstance(other, Set):
  148.             return NotImplemented
  149.         return len(self) < len(other) and self.__le__(other)
  150.  
  151.     def __gt__(self, other):
  152.         if not isinstance(other, Set):
  153.             return NotImplemented
  154.         return other < self
  155.  
  156.     def __ge__(self, other):
  157.         if not isinstance(other, Set):
  158.             return NotImplemented
  159.         return other <= self
  160.  
  161.     def __eq__(self, other):
  162.         if not isinstance(other, Set):
  163.             return NotImplemented
  164.         return len(self) == len(other) and self.__le__(other)
  165.  
  166.     def __ne__(self, other):
  167.         return not (self == other)
  168.  
  169.     @classmethod
  170.     def _from_iterable(cls, it):
  171.         '''Construct an instance of the class from any iterable input.
  172.  
  173.         Must override this method if the class constructor signature
  174.         does not accept an iterable for an input.
  175.         '''
  176.         return cls(it)
  177.  
  178.     def __and__(self, other):
  179.         if not isinstance(other, Iterable):
  180.             return NotImplemented
  181.         return self._from_iterable(value for value in other if value in self)
  182.  
  183.     def isdisjoint(self, other):
  184.         for value in other:
  185.             if value in self:
  186.                 return False
  187.         return True
  188.  
  189.     def __or__(self, other):
  190.         if not isinstance(other, Iterable):
  191.             return NotImplemented
  192.         chain = (e for s in (self, other) for e in s)
  193.         return self._from_iterable(chain)
  194.  
  195.     def __sub__(self, other):
  196.         if not isinstance(other, Set):
  197.             if not isinstance(other, Iterable):
  198.                 return NotImplemented
  199.             other = self._from_iterable(other)
  200.         return self._from_iterable(value for value in self
  201.                                    if value not in other)
  202.  
  203.     def __xor__(self, other):
  204.         if not isinstance(other, Set):
  205.             if not isinstance(other, Iterable):
  206.                 return NotImplemented
  207.             other = self._from_iterable(other)
  208.         return (self - other) | (other - self)
  209.  
  210.     # Sets are not hashable by default, but subclasses can change this
  211.     __hash__ = None
  212.  
  213.     def _hash(self):
  214.         """Compute the hash value of a set.
  215.  
  216.         Note that we don't define __hash__: not all sets are hashable.
  217.         But if you define a hashable set type, its __hash__ should
  218.         call this function.
  219.  
  220.         This must be compatible __eq__.
  221.  
  222.         All sets ought to compare equal if they contain the same
  223.         elements, regardless of how they are implemented, and
  224.         regardless of the order of the elements; so there's not much
  225.         freedom for __eq__ or __hash__.  We match the algorithm used
  226.         by the built-in frozenset type.
  227.         """
  228.         MAX = sys.maxint
  229.         MASK = 2 * MAX + 1
  230.         n = len(self)
  231.         h = 1927868237 * (n + 1)
  232.         h &= MASK
  233.         for x in self:
  234.             hx = hash(x)
  235.             h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
  236.             h &= MASK
  237.         h = h * 69069 + 907133923
  238.         h &= MASK
  239.         if h > MAX:
  240.             h -= MASK + 1
  241.         if h == -1:
  242.             h = 590923713
  243.         return h
  244.  
  245. Set.register(frozenset)
  246.  
  247.  
  248. class MutableSet(Set):
  249.  
  250.     @abstractmethod
  251.     def add(self, value):
  252.         """Add an element."""
  253.         raise NotImplementedError
  254.  
  255.     @abstractmethod
  256.     def discard(self, value):
  257.         """Remove an element.  Do not raise an exception if absent."""
  258.         raise NotImplementedError
  259.  
  260.     def remove(self, value):
  261.         """Remove an element. If not a member, raise a KeyError."""
  262.         if value not in self:
  263.             raise KeyError(value)
  264.         self.discard(value)
  265.  
  266.     def pop(self):
  267.         """Return the popped value.  Raise KeyError if empty."""
  268.         it = iter(self)
  269.         try:
  270.             value = next(it)
  271.         except StopIteration:
  272.             raise KeyError
  273.         self.discard(value)
  274.         return value
  275.  
  276.     def clear(self):
  277.         """This is slow (creates N new iterators!) but effective."""
  278.         try:
  279.             while True:
  280.                 self.pop()
  281.         except KeyError:
  282.             pass
  283.  
  284.     def __ior__(self, it):
  285.         for value in it:
  286.             self.add(value)
  287.         return self
  288.  
  289.     def __iand__(self, it):
  290.         for value in (self - it):
  291.             self.discard(value)
  292.         return self
  293.  
  294.     def __ixor__(self, it):
  295.         if not isinstance(it, Set):
  296.             it = self._from_iterable(it)
  297.         for value in it:
  298.             if value in self:
  299.                 self.discard(value)
  300.             else:
  301.                 self.add(value)
  302.         return self
  303.  
  304.     def __isub__(self, it):
  305.         for value in it:
  306.             self.discard(value)
  307.         return self
  308.  
  309. MutableSet.register(set)
  310.  
  311.  
  312. ### MAPPINGS ###
  313.  
  314.  
  315. class Mapping(Sized, Iterable, Container):
  316.  
  317.     @abstractmethod
  318.     def __getitem__(self, key):
  319.         raise KeyError
  320.  
  321.     def get(self, key, default=None):
  322.         try:
  323.             return self[key]
  324.         except KeyError:
  325.             return default
  326.  
  327.     def __contains__(self, key):
  328.         try:
  329.             self[key]
  330.         except KeyError:
  331.             return False
  332.         else:
  333.             return True
  334.  
  335.     def iterkeys(self):
  336.         return iter(self)
  337.  
  338.     def itervalues(self):
  339.         for key in self:
  340.             yield self[key]
  341.  
  342.     def iteritems(self):
  343.         for key in self:
  344.             yield (key, self[key])
  345.  
  346.     def keys(self):
  347.         return list(self)
  348.  
  349.     def items(self):
  350.         return [(key, self[key]) for key in self]
  351.  
  352.     def values(self):
  353.         return [self[key] for key in self]
  354.  
  355.     # Mappings are not hashable by default, but subclasses can change this
  356.     __hash__ = None
  357.  
  358.     def __eq__(self, other):
  359.         return isinstance(other, Mapping) and \
  360.                dict(self.items()) == dict(other.items())
  361.  
  362.     def __ne__(self, other):
  363.         return not (self == other)
  364.  
  365. class MappingView(Sized):
  366.  
  367.     def __init__(self, mapping):
  368.         self._mapping = mapping
  369.  
  370.     def __len__(self):
  371.         return len(self._mapping)
  372.  
  373.  
  374. class KeysView(MappingView, Set):
  375.  
  376.     def __contains__(self, key):
  377.         return key in self._mapping
  378.  
  379.     def __iter__(self):
  380.         for key in self._mapping:
  381.             yield key
  382.  
  383.  
  384. class ItemsView(MappingView, Set):
  385.  
  386.     def __contains__(self, item):
  387.         key, value = item
  388.         try:
  389.             v = self._mapping[key]
  390.         except KeyError:
  391.             return False
  392.         else:
  393.             return v == value
  394.  
  395.     def __iter__(self):
  396.         for key in self._mapping:
  397.             yield (key, self._mapping[key])
  398.  
  399.  
  400. class ValuesView(MappingView):
  401.  
  402.     def __contains__(self, value):
  403.         for key in self._mapping:
  404.             if value == self._mapping[key]:
  405.                 return True
  406.         return False
  407.  
  408.     def __iter__(self):
  409.         for key in self._mapping:
  410.             yield self._mapping[key]
  411.  
  412.  
  413. class MutableMapping(Mapping):
  414.  
  415.     @abstractmethod
  416.     def __setitem__(self, key, value):
  417.         raise KeyError
  418.  
  419.     @abstractmethod
  420.     def __delitem__(self, key):
  421.         raise KeyError
  422.  
  423.     __marker = object()
  424.  
  425.     def pop(self, key, default=__marker):
  426.         try:
  427.             value = self[key]
  428.         except KeyError:
  429.             if default is self.__marker:
  430.                 raise
  431.             return default
  432.         else:
  433.             del self[key]
  434.             return value
  435.  
  436.     def popitem(self):
  437.         try:
  438.             key = next(iter(self))
  439.         except StopIteration:
  440.             raise KeyError
  441.         value = self[key]
  442.         del self[key]
  443.         return key, value
  444.  
  445.     def clear(self):
  446.         try:
  447.             while True:
  448.                 self.popitem()
  449.         except KeyError:
  450.             pass
  451.  
  452.     def update(self, other=(), **kwds):
  453.         if isinstance(other, Mapping):
  454.             for key in other:
  455.                 self[key] = other[key]
  456.         elif hasattr(other, "keys"):
  457.             for key in other.keys():
  458.                 self[key] = other[key]
  459.         else:
  460.             for key, value in other:
  461.                 self[key] = value
  462.         for key, value in kwds.items():
  463.             self[key] = value
  464.  
  465.     def setdefault(self, key, default=None):
  466.         try:
  467.             return self[key]
  468.         except KeyError:
  469.             self[key] = default
  470.         return default
  471.  
  472. MutableMapping.register(dict)
  473.  
  474.  
  475. ### SEQUENCES ###
  476.  
  477.  
  478. class Sequence(Sized, Iterable, Container):
  479.     """All the operations on a read-only sequence.
  480.  
  481.     Concrete subclasses must override __new__ or __init__,
  482.     __getitem__, and __len__.
  483.     """
  484.  
  485.     @abstractmethod
  486.     def __getitem__(self, index):
  487.         raise IndexError
  488.  
  489.     def __iter__(self):
  490.         i = 0
  491.         try:
  492.             while True:
  493.                 v = self[i]
  494.                 yield v
  495.                 i += 1
  496.         except IndexError:
  497.             return
  498.  
  499.     def __contains__(self, value):
  500.         for v in self:
  501.             if v == value:
  502.                 return True
  503.         return False
  504.  
  505.     def __reversed__(self):
  506.         for i in reversed(range(len(self))):
  507.             yield self[i]
  508.  
  509.     def index(self, value):
  510.         for i, v in enumerate(self):
  511.             if v == value:
  512.                 return i
  513.         raise ValueError
  514.  
  515.     def count(self, value):
  516.         return sum(1 for v in self if v == value)
  517.  
  518. Sequence.register(tuple)
  519. Sequence.register(basestring)
  520. Sequence.register(buffer)
  521. Sequence.register(xrange)
  522.  
  523.  
  524. class MutableSequence(Sequence):
  525.  
  526.     @abstractmethod
  527.     def __setitem__(self, index, value):
  528.         raise IndexError
  529.  
  530.     @abstractmethod
  531.     def __delitem__(self, index):
  532.         raise IndexError
  533.  
  534.     @abstractmethod
  535.     def insert(self, index, value):
  536.         raise IndexError
  537.  
  538.     def append(self, value):
  539.         self.insert(len(self), value)
  540.  
  541.     def reverse(self):
  542.         n = len(self)
  543.         for i in range(n//2):
  544.             self[i], self[n-i-1] = self[n-i-1], self[i]
  545.  
  546.     def extend(self, values):
  547.         for v in values:
  548.             self.append(v)
  549.  
  550.     def pop(self, index=-1):
  551.         v = self[index]
  552.         del self[index]
  553.         return v
  554.  
  555.     def remove(self, value):
  556.         del self[self.index(value)]
  557.  
  558.     def __iadd__(self, values):
  559.         self.extend(values)
  560.         return self
  561.  
  562. MutableSequence.register(list)
  563.